package 普通数组.除自身以外数组的乘积;

/**
 * 优化思路：
 * 其实只用一个数组就够了
 * 先将前缀积保存在res数组中
 * 然后再从后向前遍历，在将后缀积与前缀积相乘保存到res数组中
 * */

class Solution1 {
    public int[] productExceptSelf(int[] nums) {
        int numsLen = nums.length;
        int[] res = new int[numsLen];
        int prefix = 1;
        for (int i = 0; i < numsLen; ++i) {
            // 正向遍历保存prefix结果到res
            res[i] = prefix;
            prefix *= nums[i];
        }
        int postfix = 1;
        for (int j = numsLen - 1; j >= 0; --j) {
            // 逆向遍历 中间结果（前缀积）乘以后缀积
            res[j] *= postfix;
            postfix *= nums[j];
        }
        return res;
    }
}